#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/09/11
# @Author   :Changshu
# @File     :practice_108.py

class TreeNode:
	def __init__(self, x):
		self.val = x
		self.left = None
		self.right = None


# 前序打印
def preOrder(root):
	if root != None:
		print(root.val, end=' ')
		preOrder(root.left)
		preOrder(root.right)


def sortedArrayToBST(nums) -> TreeNode:
	return arrayToBST(nums, 0, len(nums) - 1)


def arrayToBST(nums, l, r):
	if r < l:
		return None
	mid = l + ((r - l) >>2)
	root = TreeNode(nums[mid])
	root.left = arrayToBST(nums, l, mid - 1)
	root.right = arrayToBST(nums, mid + 1, r)
	return root


if __name__ == '__main__':
	# root = TreeNode(0)
	# node1_1=TreeNode(-3)
	# node1_2=TreeNode(9)
	#
	# root.left=node1_1
	# root.right=node1_2
	#
	# node2_1=TreeNode(-10)
	# node2_2 = TreeNode(5)
	# node1_1.left=node2_1
	# node1_2.left=node2_2
	#
	# preOrder(root)

	nums = [-10, -3, 0, 5, 9]
	root = sortedArrayToBST(nums)
	preOrder(root)
